package 程序员面试金典;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 04.06. 后继者
 * 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
 *
 * 如果指定节点没有对应的“下一个”节点，则返回null。
 *
 * 示例 1:
 *
 * 输入: root = [2,1,3], p = 1
 *
 *   2
 *  / \
 * 1   3
 *
 * 输出: 2
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], p = 6
 *
 *       5
 *      / \
 *     3   6
 *    / \
 *   2   4
 *  /
 * 1
 *
 * 输出: null
 */
public class T04_06 {
   List<TreeNode> temp = new ArrayList<TreeNode>();
    //中序遍历 找后一个节点
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root);

        for (int i = 0; i < temp.size()-1; i++) {
            if (temp.get(i)==p){
                return temp.get(i+1);
            }
        }

        return null;


    }

    //中序遍历
    public void dfs(TreeNode root){
        if (root==null){
            return;
        }
        dfs(root.left);
        temp.add(root);
        dfs(root.right);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
